'''
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
'''


class TreeNode:
    def __init__(self,val,left,right) -> None:
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)

        root.left = right
        root.right = left

        return root
    
    def invertTree2(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        
        self.traverse(root)
        return root
        
    
    def traverse(self,root):
        if root is None:
            return None
        
        t = root.left
        root.left = root.right
        root.right = t
        self.traverse(root.left)
        self.traverse(root.right)
